package bookForJava.P4;

import static other.QuickSortPractice.QuickSortPractice1;

public class P4_5 {
	static final int SIZE=100;
	static int i=0;
	static int j=0;

	static void quickSort1(int[] arr,int left,int right)			//快速排序算法
	{
	    int f,t;
		int rtemp,ltemp;

	    ltemp=left;
	    rtemp=right;
	    f=arr[(left+right)/2];						//分界值
		while(ltemp<rtemp)
		{
	        while(arr[ltemp]<f)
			{
				++ltemp;
			}
	        while(arr[rtemp]>f) 
			{
				--rtemp;
			}
	        if(ltemp<=rtemp)
	        {
				t=arr[ltemp];
		        arr[ltemp]=arr[rtemp];
	    	    arr[rtemp]=t;
				--rtemp;
	        	++ltemp;
			}
	    }
	    if(ltemp==rtemp) 
		{
			ltemp++;
		}

	    if(left<rtemp) 
		{
			quickSort(arr,left,ltemp-1);			//递归调用
		}
	    if(ltemp<right) 
		{
			quickSort(arr,rtemp+1,right);			//递归调用
		}
	}

	static void quickSort(int[] a,int low,int high){
		int start = low;
		int end = high;
		int key = a[low];


		while(end>start){
			//从后往前比较
			while(end>start&&a[end]>=key)  //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
				end--;
			if(a[end]<key){
				int temp = a[end];
				a[end] = a[start];
				a[start] = temp;
			}

			System.out.print("第"+(++i)+"步排序结果:");			//输出每步排序的结果
			for(int h=low;h<(high+1);h++)
			{
				System.out.print(" "+a[h]);				//输出
			}
			System.out.print("\n");

			//从前往后比较
			while(end>start&&a[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
				start++;
			if(a[start]>key){
				int temp = a[start];
				a[start] = a[end];
				a[end] = temp;
			}

			System.out.print("第"+(++i)+"步排序结果:");			//输出每步排序的结果
			for(int h=low;h<(high+1);h++)
			{
				System.out.print(" "+a[h]);				//输出
			}
			System.out.print("\n");

			//此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
		}
		System.out.print("第"+(++j)+"次递归调用;"+"start:"+(start)+";end:"+(end)+";low:"+(low)+";high:"+(high)+"\n");
		//递归
		if(start>low) quickSort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
		if(end<high) quickSort(a,end+1,high);//右边序列。从关键值索引+1到最后一个
	}

	public static void main(String[] args) 
	{
		int[] shuzu=new int[SIZE];
		int i;
		
		for(i=0;i<SIZE;i++)
		{
			shuzu[i]=(int)(Math.random()*(100+1));			//初始化数组
		}
		
		System.out.print("排序前的数组为：\n");				//输出排序前的数组
		for(i=0;i<SIZE;i++)
		{
			System.out.print(shuzu[i]+" ");
		}
		System.out.print("\n");

		QuickSortPractice1(shuzu,0,SIZE-1);					//排序操作
//		quickSort(shuzu,0,SIZE-1);					//排序操作
		
		System.out.print("排序后的数组为：\n");
		for(i=0;i<SIZE;i++)
		{
			System.out.print(shuzu[i]+" ");					//输出排序后的数组
		}
		System.out.print("\n");

	}

}
